#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    unordered_map<int, int> inorderIndex;

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) {
            inorderIndex[inorder[i]] = i;
        }

        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder, int inorderLeft, int inorderRight, int preorderLeft, int preorderRignt) {
        if ((inorderLeft > inorderRight) || (preorderLeft > preorderRignt)) {
            return nullptr;
        }

        int rootVal = preorder[preorderLeft];
        TreeNode* root = new TreeNode(rootVal);
        int leftChildrenLen = inorderIndex[rootVal] - inorderLeft;
        int rightChildrenLen = inorderRight - inorderIndex[rootVal];

        TreeNode* leftChild = myBuildTree(preorder, inorder, inorderLeft, inorderIndex[rootVal] - 1, preorderLeft + 1, preorderLeft + leftChildrenLen);
        TreeNode* rightChild = myBuildTree(preorder, inorder, inorderIndex[rootVal] + 1, inorderRight, preorderLeft + leftChildrenLen + 1, preorderRignt);

        root->left = leftChild;
        root->right = rightChild;
        return root;
    }
};
